import java.util.ArrayList;
import java.util.Arrays;

/**
 * 递归、回溯
 */
public class Main6 {

    /**
     * 没有重复项数字的全排列
     */
    private void swap(ArrayList<Integer> num, int i1, int i2) {
        int tmp = num.get(i1);
        num.set(i1, num.get(i2));
        num.set(i2, tmp);
    }
    public void recursion(ArrayList<ArrayList<Integer>> ret, ArrayList<Integer> num, int index) {
        //分支进入结尾，找到一种排序
        if(index == num.size() - 1) {
            ret.add(num);
        }else {
            //遍历后续的元素
            for(int i = index; i < num.size(); i++) {
                //交换二者
                swap(num, i, index);
                //继续往后找
                recursion(ret, num, index + 1);
                //回溯
                swap(num, i, index);
            }
        }
    }
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        // write code here
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        ArrayList<Integer> nums = new ArrayList<>();
        //数组转ArrayList
        for(int i = 0; i < num.length; i++) {
            nums.add(num[i]);
        }
        recursion(ret, nums, 0);
        return ret;
    }





















}
